/*
 *  linux/mm/memory.c
 *
 *  (C) 1991  Linus Torvalds
 */

/*
 * demand-loading started 01.12.91 - seems it is high on the list of
 * things wanted, and it should be easy to implement. - Linus
 */

/*
 * Ok, demand-loading was easy, shared pages a little bit tricker. Shared
 * pages started 02.12.91, seems to work. - Linus.
 *
 * Tested sharing by executing about 30 /bin/sh: under the old kernel it
 * would have taken more than the 6M I have free, but it worked well as
 * far as I could see.
 *
 * Also corrected some "invalidate()"s - I wasn't doing enough of them.
 */

/*
 * Real VM (paging to/from disk) started 18.12.91. Much more work and
 * thought has to go into this. Oh, well..
 * 19.12.91  -  works, somewhat. Sometimes I get faults, don't know why.
 *		Found it. Everything seems to work now.
 * 20.12.91  -  Ok, making the swap-device changeable like the root.
 */

#include <signal.h>

#include <asm/system.h>

#include <linux/sched.h>
#include <linux/head.h>
#include <linux/kernel.h>

#define CODE_SPACE(addr) ((((addr)+4095)&~4095) < \
current->start_code + current->end_code)

unsigned long HIGH_MEMORY = 0;

#define copy_page(from,to) \
__asm__("cld ; rep ; movsl"::"S" (from),"D" (to),"c" (1024):"cx","di","si")

unsigned char mem_map [ PAGING_PAGES ] = {0,};

/*
 * Free a page of memory at physical address 'addr'. Used by
 * 'free_page_tables()'
 */
void free_page(unsigned long addr)
{
	if (addr < LOW_MEM) return; /* addr小于LOW_MEM，说明是内核空间 */
	if (addr >= HIGH_MEMORY)    /* addr大于HIGH_MEM，说明不存在 */
		panic("trying to free nonexistent page");
	addr -= LOW_MEM;    /* mem_map管理的内存是1M以上的，所以这里要减去1M */
	addr >>= 12;    /* 得到addr所在页面 */
	if (mem_map[addr]--) return; /* 该页面mem_map不为0，减一返回 */
	mem_map[addr]=0;    /* 到这里说明mem_map本来就是0，释放空闲页面说明有问题，因为上面把0也减1了，所以这里再设置为0 */
	panic("trying to free free page");  /* 显示panic信息并停机 */
}

/*
 * This function frees a continuos block of page tables, as needed
 * by 'exit()'. As does copy_page_tables(), this handles only 4Mb blocks.
 */
int free_page_tables(unsigned long from,unsigned long size)
{
	unsigned long *pg_table;
	unsigned long * dir, nr;

	if (from & 0x3fffff)    /* 4M对齐 */
		panic("free_page_tables called with wrong alignment");
	if (!from)  /* 为0是内核空间 */
		panic("Trying to free up swapper memory space");
	size = (size + 0x3fffff) >> 22; /* 由size计算多少个4M，也是占用的页目录项数，或者页表数 */
	dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */ /* from是线性地址，from>>22是页目录项，因为页目录项从0开始，且每项4字节，所以页目录项<<2页目录指针 */
	for ( ; size-->0 ; dir++) {
		if (!(1 & *dir))    /* P为0，说明该页目录项无效，即对应的页表不存在 */
			continue;
		pg_table = (unsigned long *) (0xfffff000 & *dir);   /* 得到页表首地址 */
		for (nr=0 ; nr<1024 ; nr++) {   /* 每个页表4K，每个页表项4字节，所以共有1024个页表项，即1024个页面 */
			if (*pg_table) {
				if (1 & *pg_table)  /* P为1，说明页面存在 */
					free_page(0xfffff000 & *pg_table);  /* 释放页面 */
				else    /* P为0，有可能被交换出去了，要到swap中释放 */
					swap_free(*pg_table >> 1);
				*pg_table = 0;
			}
			pg_table++; /* 下一个页表项 */
		}
		free_page(0xfffff000 & *dir);   /* 最后释放页表 */
		*dir = 0;
	}
	invalidate();   /* 刷新cpu页变换高速缓存 */
	return 0;
}

/*
 *  Well, here is one of the most complicated functions in mm. It
 * copies a range of linerar addresses by copying only the pages.
 * Let's hope this is bug-free, 'cause this one I don't want to debug :-)
 *
 * Note! We don't copy just any chunks of memory - addresses have to
 * be divisible by 4Mb (one page-directory entry), as this makes the
 * function easier. It's used only by fork anyway.
 *
 * NOTE 2!! When from==0 we are copying kernel space for the first
 * fork(). Then we DONT want to copy a full page-directory entry, as
 * that would lead to some serious memory waste - we just copy the
 * first 160 pages - 640kB. Even that is more than we need, but it
 * doesn't take any more memory - we don't copy-on-write in the low
 * 1 Mb-range, so the pages can be shared with the kernel. Thus the
 * special case for nr=xxxx.
 */
int copy_page_tables(unsigned long from,unsigned long to,long size)
{
	unsigned long * from_page_table;
	unsigned long * to_page_table;
	unsigned long this_page;
	unsigned long * from_dir, * to_dir;
	unsigned long new_page;
	unsigned long nr;

	if ((from&0x3fffff) || (to&0x3fffff))   /* 一个页表管理4M内存，所以低22bit为0 */
		panic("copy_page_tables called with wrong alignment");
	from_dir = (unsigned long *) ((from>>20) & 0xffc); /* _pg_dir = 0 */    /* 源页目录，低12位为属性位 */
	to_dir = (unsigned long *) ((to>>20) & 0xffc);      /* 目的页目录 */
	size = ((unsigned) (size+0x3fffff)) >> 22;  /* 计算需要拷贝的页表数（页目录数），因为一个页表可管理4M内存，所以用(size+(4M-1)) >> 22 */
	for( ; size-->0 ; from_dir++,to_dir++) {
		if (1 & *to_dir)    /* 目的页目录的P=1说明已经存在 */
			panic("copy_page_tables: already exist");
		if (!(1 & *from_dir))   /* 源页目录的P=0，则跳过 */
			continue;
		from_page_table = (unsigned long *) (0xfffff000 & *from_dir);   /* 源页表地址 */
		if (!(to_page_table = (unsigned long *) get_free_page()))   /* 为目的页表申请一页空间 */
			return -1;	/* Out of memory, see freeing */
		*to_dir = ((unsigned long) to_page_table) | 7;  /* 把申请的目的页表登记到目的页目录中，并设置用户（user），可读写(R/W)，存在(P)标志 */
		nr = (from==0)?0xA0:1024;   /* 设置需要复制的页面数，如果在内核空间，仅需要复制头160页对应的页表项，对应于开始640KB物理内存，否则需要复制一个页表中所有1024个页表项，对应4M物理内存 */
		for ( ; nr-- > 0 ; from_page_table++,to_page_table++) {
			this_page = *from_page_table;
			if (!this_page) /* 当前源页面没有使用 */
				continue;
			if (!(1 & this_page)) { /* 该页表项有内容，但是P=0，说明可能在交换设备中，申请一页内存从交换设备读入该页面，然后将该页表项复制到目的页表项中 */
				if (!(new_page = get_free_page()))  /* 申请一页内存 */
					return -1;
				read_swap_page(this_page>>1, (char *) new_page);    /* 从交换设备中读出该页面到申请的内存中 */
				*to_page_table = this_page; /* 将该页表项复制到目的页表项中 */
				*from_page_table = new_page | (PAGE_DIRTY | 7); /* 修改源页表项指向申请的内存，并把D标志以及user、r/w、P置位 */
				continue;
			}
			this_page &= ~2;    /* 否则把该页表项中的R/W设为只读 */
			*to_page_table = this_page;
			if (this_page > LOW_MEM) {  /* 位于1M以上，说明在主内存区，需要设置mem_map，这种情况需要在进程调用execve()并装载执行了新程序代码时才会执行，任务0创建任务1不会执行这里 */
				*from_page_table = this_page;   /* 令源页表项也只读，因为现在开始已有两个进程公用内存区了，若其中一个进程需要进行写操作，则可以通过页异常写保护处理为执行写操作的进程分配内存 */
				this_page -= LOW_MEM;   /* mem_map[]管理1M~16M空间，所以这里要减去1M */
				this_page >>= 12;
				mem_map[this_page]++;
			}
		}
	}
	invalidate();   /* 刷新页变换高速缓冲 */
	return 0;
}

/*
 * This function puts a page in memory at the wanted address.
 * It returns the physical address of the page gotten, 0 if
 * out of memory (either when trying to access page-table or
 * page.)
 */
static unsigned long put_page(unsigned long page,unsigned long address)
{
	unsigned long tmp, *page_table;

/* NOTE !!! This uses the fact that _pg_dir=0 */

	if (page < LOW_MEM || page >= HIGH_MEMORY)  /* 验证物理页面地址，给出警告 */
		printk("Trying to put page %p at %p\n",page,address);
	if (mem_map[(page-LOW_MEM)>>12] != 1)   /* 判断该页面是否已申请，没有申请给出警告 */
		printk("mem_map disagrees with %p at %p\n",page,address);
	page_table = (unsigned long *) ((address>>20) & 0xffc); /* 指向页目录 */
	if ((*page_table)&1)    /* 页表存在 */
		page_table = (unsigned long *) (0xfffff000 & *page_table); /* 指向页表首地址 */
	else {  /* 页表不存在 */
		if (!(tmp=get_free_page())) /* 申请页面，用作页表 */
			return 0;
		*page_table = tmp | 7;  /* 在页目录中设置页表地址，user-读写-存在位 */
		page_table = (unsigned long *) tmp; /* 指向页表首地址 */
	}
	page_table[(address>>12) & 0x3ff] = page | 7;   /* 设置页表的值，这样就可以将物理页面映射到具体的页表项中，即映射到线性地址中 */
/* no need for invalidate */
	return page;    /* 返回物理页面地址 */
}

/*
 * The previous function doesn't work very well if you also want to mark
 * the page dirty: exec.c wants this, as it has earlier changed the page,
 * and we want the dirty-status to be correct (for VM). Thus the same
 * routine, but this time we mark it dirty too.
 */
unsigned long put_dirty_page(unsigned long page, unsigned long address)
{
	unsigned long tmp, *page_table;

/* NOTE !!! This uses the fact that _pg_dir=0 */

	if (page < LOW_MEM || page >= HIGH_MEMORY)
		printk("Trying to put page %p at %p\n",page,address);
	if (mem_map[(page-LOW_MEM)>>12] != 1)
		printk("mem_map disagrees with %p at %p\n",page,address);
	page_table = (unsigned long *) ((address>>20) & 0xffc);
	if ((*page_table)&1)
		page_table = (unsigned long *) (0xfffff000 & *page_table);
	else {
		if (!(tmp=get_free_page()))
			return 0;
		*page_table = tmp|7;
		page_table = (unsigned long *) tmp;
	}
	page_table[(address>>12) & 0x3ff] = page | (PAGE_DIRTY | 7);    /* 与上面一个函数相比，多设置了一个页面已修改标志 */
/* no need for invalidate */
	return page;
}

void un_wp_page(unsigned long * table_entry)
{
	unsigned long old_page,new_page;

	old_page = 0xfffff000 & *table_entry;   /* 页面地址 */
	if (old_page >= LOW_MEM && mem_map[MAP_NR(old_page)]==1) {  /* 在主内存区且没有被共享 */
		*table_entry |= 2; /* 设置读写权限 */
		invalidate();
		return;
	}
	if (!(new_page=get_free_page()))    /* 页面被共享了，需要申请新页面 */
		oom();
	if (old_page >= LOW_MEM)    /* 原页面在主内存区 */
		mem_map[MAP_NR(old_page)]--;    /* 把原页面mem_map引用减1 */
	copy_page(old_page,new_page);   /* 把原页面拷贝到申请的新页面 */
	*table_entry = new_page | 7;    /* 设置页表为新页面+user+r/w+P */
	invalidate();
}	

/*
 * This routine handles present pages, when users try to write
 * to a shared page. It is done by copying the page to a new address
 * and decrementing the shared-page counter for the old page.
 *
 * If it's in code space we exit with a segment error.
 */
void do_wp_page(unsigned long error_code,unsigned long address) /* 参数由CPU产生异常自动生成的，CR2寄存器给出引起异常的线性地址 */
{
	if (address < TASK_SIZE)    /* 小于64M，说明在内核或进程0和进程1的地址范围内，是写保护的，发出警告 */
		printk("\n\rBAD! KERNEL MEMORY WP-ERR!\n\r");
	if (address - current->start_code > TASK_SIZE) {    /* 线性地址超出产生异常的进程的地址空间，直接退出 */
		printk("Bad things happen: page error in do_wp_page\n\r");
		do_exit(SIGSEGV);
	}
#if 0
/* we cannot do this yet: the estdio library writes to code space */
/* stupid, stupid. I really want the libc.a from GNU */
	if (CODE_SPACE(address))    /* 如果线性地址在代码地址空间内，就退出，因为代码是只读的，estdio库会在代码地址空间写，所以这里注释掉了 */
		do_exit(SIGSEGV);
#endif
	un_wp_page((unsigned long *)
		(((address>>10) & 0xffc) + (0xfffff000 &
		*((unsigned long *) ((address>>20) &0xffc))))); /* 处理页面保护 */

}

void write_verify(unsigned long address)
{
	unsigned long page;

	if (!( (page = *((unsigned long *) ((address>>20) & 0xffc)) )&1))   /* 判断页表是否存在 */
		return;
	page &= 0xfffff000; /* 取得页面首地址 */
	page += ((address>>10) & 0xffc);    /* 取得页内偏移 */
	if ((3 & *(unsigned long *) page) == 1)  /* non-writeable, present */
		un_wp_page((unsigned long *) page); /* 取消写保护 */
	return;
}

void get_empty_page(unsigned long address)
{
	unsigned long tmp;

	if (!(tmp=get_free_page()) || !put_page(tmp,address)) { /* 申请物理页面并映射到线性地址上 */
		free_page(tmp);		/* 0 is ok - ignored */ /* tmp是0也没有关系，free_page函数会忽略它 */
		oom();
	}
}

/*
 * try_to_share() checks the page at address "address" in the task "p",
 * to see if it exists, and if it is clean. If so, share it with the current
 * task.
 *
 * NOTE! This assumes we have checked that p != current, and that they
 * share the same executable or library.
 */
static int try_to_share(unsigned long address, struct task_struct * p)
{
	unsigned long from;
	unsigned long to;
	unsigned long from_page;
	unsigned long to_page;
	unsigned long phys_addr;

	from_page = to_page = ((address>>20) & 0xffc);  /* 逻辑地址中的页目录项，在进程空间0-64M算出的页目录项 */
	from_page += ((p->start_code>>20) & 0xffc); /* from_page再加上进程p在4G地址空间的起始地址对应的页目录项，得到进程p中的逻辑地址在4G空间的页目录项 */
	to_page += ((current->start_code>>20) & 0xffc); /* to_page再加上当前进程在4G地址空间的起始地址对应的页目录项，得到当前进程中的逻辑地址在4G空间的页目录项 */
/* is there a page-directory at from? */
	from = *(unsigned long *) from_page;    /* 取出页目录内容 */
	if (!(from & 1))    /* 对应的页表是否存在 */
		return 0;
	from &= 0xfffff000; /* 得到页表首地址 */
	from_page = from + ((address>>10) & 0xffc); /* 加上address的页表偏移地址，得到address对应的页表的地址 */
	phys_addr = *(unsigned long *) from_page;   /* 取出页表内容 */
/* is the page clean and present? */
	if ((phys_addr & 0x41) != 0x01) /* 判断已修改位和存在位，存在且未被修改才会往下执行，否则直接返回 */
		return 0;
	phys_addr &= 0xfffff000;    /* 得到页面首地址 */
	if (phys_addr >= HIGH_MEMORY || phys_addr < LOW_MEM)    /* 判断页面地址是否有效 */
		return 0;
	to = *(unsigned long *) to_page;    /* 取出页目录内容 */
	if (!(to & 1))  /* 判断页表是否存在 */
		if (to = get_free_page())   /* 不存在申请一页 */
			*(unsigned long *) to_page = to | 7;    /* 设置页目录内容 */
		else
			oom();
	to &= 0xfffff000;   /* 页表首地址 */
	to_page = to + ((address>>10) & 0xffc); /* 得到address在当前进程中对应的页表地址 */
	if (1 & *(unsigned long *) to_page) /* 判断页面是否存在，如果存在死机处理 */
		panic("try_to_share: to_page already exists");
/* share them: write-protect */
	*(unsigned long *) from_page &= ~2; /* 清除可写位 */
	*(unsigned long *) to_page = *(unsigned long *) from_page;  /* 拷贝页表内容 */
	invalidate();
	phys_addr -= LOW_MEM;
	phys_addr >>= 12;   /* 这两句得到页面的mem_map下标 */
	mem_map[phys_addr]++;   /* 共享成功，把mem_map++ */
	return 1;
}

/*
 * share_page() tries to find a process that could share a page with
 * the current one. Address is the address of the wanted page relative
 * to the current data space.
 *
 * We first check if it is at all feasible by checking executable->i_count.
 * It should be >1 if there are other tasks sharing this inode.
 */
static int share_page(struct m_inode * inode, unsigned long address)
{
	struct task_struct ** p;

	if (inode->i_count < 2 || !inode)   /* 通过i节点计数值判断有几个进程在执行该执行文件，或者inode是否有效 */
		return 0;
	for (p = &LAST_TASK ; p > &FIRST_TASK ; --p) {  /* 遍历进程数组 */
		if (!*p)    /* 判断进程是否存在 */
			continue;
		if (current == *p)  /* 判断是否为当前进程 */
			continue;
		if (address < LIBRARY_OFFSET) { /* 判断逻辑地址address是否在进程的库文件地址范围内 */
			if (inode != (*p)->executable)  /* 如果不在库文件地址空间，说明在可执行文件地址空间，判断inode是否为可执行文件 */
				continue;
		} else {
			if (inode != (*p)->library) /* 在库文件地址空间，判断inode是否为库 */
				continue;
		}
		if (try_to_share(address,*p))   /* 可以试着共享了 */
			return 1;
	}
	return 0;
}

void do_no_page(unsigned long error_code,unsigned long address)
{
	int nr[4];
	unsigned long tmp;
	unsigned long page;
	int block,i;
	struct m_inode * inode;

	if (address < TASK_SIZE)
		printk("\n\rBAD!! KERNEL PAGE MISSING\n\r");
	if (address - current->start_code > TASK_SIZE) {
		printk("Bad things happen: nonexistent page error in do_no_page\n\r");
		do_exit(SIGSEGV);
	}
	page = *(unsigned long *) ((address >> 20) & 0xffc);    /* 得到页目录项 */
	if (page & 1) { /* 页表存在 */
		page &= 0xfffff000; /* 得到页表首地址 */
		page += (address >> 10) & 0xffc;    /* 得到页表项 */
		tmp = *(unsigned long *) page;  /* 页表内容 */
		if (tmp && !(1 & tmp)) {    /* 页表项内容不为0，存在位为0，说明页面在交换设备中 */
			swap_in((unsigned long *) page);    /* 从交换设备读进来 */
			return;
		}
	}
	address &= 0xfffff000;  /* 页表不存在或者页面不存在，获取address对应的页面首地址 */
	tmp = address - current->start_code;    /* 得到逻辑地址 */
	if (tmp >= LIBRARY_OFFSET ) {   /* 逻辑地址在库文件地址空间 */
		inode = current->library;
		block = 1 + (tmp-LIBRARY_OFFSET) / BLOCK_SIZE;  /* block大小是1K，第一块是头文件，所以这里要加1 */
	} else if (tmp < current->end_data) {   /* 逻辑地址在可执行文件地址空间 */
		inode = current->executable;
		block = 1 + tmp / BLOCK_SIZE;
	} else {    /* 用户动态申请 */
		inode = NULL;
		block = 0;
	}
	if (!inode) {
		get_empty_page(address);    /* 动态申请的空间，就需要为address申请新的页面 */
		return;
	}
	if (share_page(inode,tmp))  /* 如果在库文件和可执行文件地址空间就可以共享页面 */
		return;
	if (!(page = get_free_page()))  /* 共享失败就要申请新的页面 */
		oom();
/* remember that 1 block is used for header */
	for (i=0 ; i<4 ; block++,i++)
		nr[i] = bmap(inode,block);  /* 根据inode和block可以从映射位图中找到对应块设备中对应的设备逻辑块号（保存在nr[]数组中）*/
	bread_page(page,inode->i_dev,nr);   /* 把这4个逻辑块读到page中 */
	i = tmp + 4096 - current->end_data; /* 超出执行文件end_data以后的部分，后面将这个页面无用的部分清零 */
	if (i>4095) /* 离末端大于1页，无需清零 */
		i = 0;
	tmp = page + 4096;  /* 让tmp指向要清零的地方 */
	while (i-- > 0) {
		tmp--;
		*(char *)tmp = 0;   /* 清零操作 */
	}
	if (put_page(page,address)) /* 把页面映射到线性地址address处 */
		return;
	free_page(page);    /* 如果映射失败释放该页 */
	oom();
}

void mem_init(long start_mem, long end_mem)
{
	int i;

	HIGH_MEMORY = end_mem;
	for (i=0 ; i<PAGING_PAGES ; i++)    /* 1MB~16MB共有3840个页面, 0~1MB用于内核系统(0~640Kb用于内核，剩下的是高速缓冲和设备内存) */
		mem_map[i] = USED;      /* 先把所有页面初始化为USED */
	i = MAP_NR(start_mem);      /* (start_mem-1MB) >> 12, 计算主内存区从1MB开始所对应的mem_map下标 */
	end_mem -= start_mem;       /* 主内存区大小 */
	end_mem >>= 12;             /* 主内存区页面数 */
	while (end_mem-->0)
		mem_map[i++]=0;         /* 将主内存区所有页面初始化为0，这样一来，1MB~主内存区是USED，主内存区是0 */
}

void show_mem(void)
{
	int i,j,k,free=0,total=0;
	int shared=0;
	unsigned long * pg_tbl;

	printk("Mem-info:\n\r");
	for(i=0 ; i<PAGING_PAGES ; i++) {   /* 在用于分页的主内存区中查找内存信息 */
		if (mem_map[i] == USED) /* 跳过标记为USED的内存，这部分在mem_init中是1M以上的系统占用的内存 */
			continue;
		total++;    /* 统计主内存页面数 */
		if (!mem_map[i])    /* 未使用内存页面数 */
			free++;
		else    /* 使用的内存 */
			shared += mem_map[i]-1; /* 统计共享的页面数 */
	}
	printk("%d free pages of %d\n\r",free,total);   /* 显示空闲内存和总内存 */
	printk("%d pages shared\n\r",shared);   /* 显示共享内存 */
	k = 0;  /* 用于统计进程页面数 */
	for(i=4 ; i<1024 ;) {   /* 这里统计逻辑页面数，页目录前4项是内核使用的，所以这里从第5项开始下标为4 */
		if (1&pg_dir[i]) {  /* 页目录项管理的二级页表是否存在 */
			if (pg_dir[i]>HIGH_MEMORY) {    /* 二级页表大于最大物理内存，说明有问题 */
				printk("page directory[%d]: %08X\n\r",
					i,pg_dir[i]);
				continue;   /* 显示信息之后，跳过该项 */
			}
			if (pg_dir[i]>LOW_MEM)  /* 页表地址大于1M，进行统计 */
				free++,k++;
			pg_tbl=(unsigned long *) (0xfffff000 & pg_dir[i]);  /* 得到页表地址 */
			for(j=0 ; j<1024 ; j++) /* 每个页表1024个页表项，即可管理1024个页面 */
				if ((pg_tbl[j]&1) && pg_tbl[j]>LOW_MEM) /* 对应的页面存在，且页面地址大于1M */
					if (pg_tbl[j]>HIGH_MEMORY)  /* 页面地址是否大于最大内存 */
						printk("page_dir[%d][%d]: %08X\n\r",
							i,j, pg_tbl[j]); /* 大于最大内存显示信息，不进行处理 */
					else    /* 小于最大内存，进行统计 */
						k++,free++;
		}
		i++;    /* 统计下一个页目录项 */
		if (!(i&15) && k) { /* 每个进程64M，占用16个页目录项，所以这里判断进程页目录项是否统计完了，k不为0，表示进程存在 */
			k++,free++;	/* one page/process for task_struct */
			printk("Process %d: %d pages\n\r",(i>>4)-1,k);  /* 显示信息 */
			k = 0;  /* 清空k，继续统计下一个进程 */
		}
	}
	printk("Memory found: %d (%d)\n\r",free-shared,total);
}
